Code Excursion

Algorithmathon Day 7: Double Linked List Flattening

Created: 19 July 2013 Modified:

Today’s goal is to flatten a list of lists into one long list. This means in addition to having a prev_node and next_node attribute the element will also have a child attribute which may or may not point to another list. An Illustration of this is below.

We will be using the Double Linked List (DoLL) base code from Day 6. Follow this link for Algorithmathon Rules. The Source Code is also available. Adding the child attribute to the element would be a good first step. We should write a test and the code to satisfy it as shown below.

double_linked_list_element_spec.rb (excerpt)

require 'spec_helper'
# code omitted here
    it "should have a 'child' method" do
      DoubleLinkedListElement.method_defined?(:child).should be_true
    end
# code omitted here

double_linked_list_element.rb

require 'spec_helper'
class DoubleLinkedListElement
  attr_accessor :next_node, :prev_node, :child, :data

  def initialize(data=nil,next_node=nil,prev_node=nil,child=nil)
    self.data=data
    self.next_node=next_node
    self.prev_node=prev_node
    self.child=child
  end
end

In order to adequately test that the list flattening is working as desired we need a list that isn’t flat. Since we will need this list in multiple tests the best way to handle this is to use helper methods. Building such a list could be error prone and we should build a test to verify our list is constructed correctly.

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should build a non flat list correctly" do
      list = build_master_list()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(4).child.length().should == 8
      list.element_at(11).child.length().should == 16
    end         
# code omitted here

With the failing test written we can now write our helpers to construct our list.

spec_helper.rb

$LOAD_PATH.unshift File.expand_path('lib')

require 'double_linked_list'
require 'double_linked_list_element'



def add_elements(the_list)
  the_list.add(DoubleLinkedListElement.new("one"))
  the_list.add(DoubleLinkedListElement.new("two"))
  the_list.add(DoubleLinkedListElement.new("three"))
  the_list.add(DoubleLinkedListElement.new("four"))
end

def build_list(number_list)
  the_list=DoubleLinkedList.new()
  number_list.each { | the_number |
    the_list.add(DoubleLinkedListElement.new(the_number.to_s))
  }
  the_list
end

def build_master_list()
  the_list=build_list((1..12))
  the_list.element_at(0).child=build_list(13..18)
  the_list.element_at(4).child=build_list(19..26)
  the_list.element_at(11).child=build_list(27..42)
  the_list
end

The uneven list builder constructed we should move onto writing tests which give our expectations of the flatten! method.

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should have a length of 42 when it receives the 'flatten!' message" do
      list = build_master_list()
      list.flatten!()
      list.length().should == 42
    end 

    it "should return '13' when it receives the message 'element_at(12).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(1).data.should == '13'
    end 

    it "should return '18' when it receives the message 'element_at(6).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(6).data.should == '18'
    end

    it "should return '2' when it receives the message 'element_at(7).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(7).data.should == '2'
    end   
# code omitted here

The tests are all passing. It’s Miller time! Kicking back with my BBC Bourbon Barrel Stout, I discuss what we have done so far. You of course are welcome to drink the beverage of your choice:) Suddenly, we realize we haven’t accounted for a child who also has a child! This means we will need to go back and update our tests and the helper methods. Methods which are capable of handling a structure similar to the one illustrated below.

Double Link List with children having children

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should build a non flat list correctly" do
      list = build_master_list()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(0).child.last().child.length().should == 8
      list.element_at(4).child.length().should == 8
      list.element_at(4).child.element_at(2).child.length().should == 8
      list.element_at(11).child.length().should == 3
      list.element_at(11).child.element_at(0).child.length().should == 6
    end          
# code omitted here

spec_helper.rb (excerpt)

# code omitted here
def build_master_list()
  the_list=build_list((1..12))
  first_child_list=build_list(13..18)
  second_child_list=build_list(19..26)
  first_child_list.last().child=second_child_list
  the_list.element_at(0).child=first_child_list

  first_child_list=build_list(27..34)
  second_child_list=build_list(35..42)
  first_child_list.element_at(2).child=second_child_list
  the_list.element_at(4).child=first_child_list


  first_child_list=build_list(43..45)
  second_child_list=build_list(46..51)
  first_child_list.element_at(0).child=second_child_list  
  the_list.element_at(11).child=first_child_list
  the_list
end
# code omitted here

We now have a list that has children which in turn also have children. Unfortunately tests that are already written are now failing and new tests need to be written. Being RSpecofiles (™ pending) we hop right into some tests.

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should have a length of 51 when it receives the 'flatten!' message" do
      list = build_master_list()
      list.flatten!()
      list.length().should == 51
    end 

    it "should return '13' when it receives the message 'element_at(12).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(1).data.should == '13'
    end 

    it "should return '18' when it receives the message 'element_at(6).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(6).data.should == '18'
    end

    it "should return '19' when it receives the message 'element_at(7).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(7).data.should == '19'
    end 

    it "should return '5' when it receives the message 'element_at(18).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(18).data.should == '5'
    end

    it "should return '27' when it receives the message 'element_at(19).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(19).data.should == '27'
    end


    it "should return '51' when it receives the message 'element_at(48).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(48).data.should == '51'
    end 

    it "should return '45' when it receives the message 'element_at(50).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(50).data.should == '45'
    end
# code omitted here

Several tests are failing and we need to update the code in our DoLL by rewriting the flatten_by_recursion method.

double_linked_list.rb (excerpt)

# code omitted here
  def flatten_by_recursion(element)
    unless element.nil?
      if element.child.nil?
        flatten_by_recursion(element.next_node)
      else
        relink(element)
        flatten_by_recursion(element.next_node)
      end
    end
  end

  def relink(element)
    tail = element.child.last()
    head = element.child.element_at(0)
    next_node = element.next_node
    element.next_node=head
    tail.next_node=next_node
    @length = @length + element.child.length()
  end
# code omitted here

All our tests are passing and this looks like a good place to stop. Tomorrow we will look into adding an unflatten! method.

tags: Algorithm - Algorithmathon - Double Linked List - RSpec - Ruby